package algorithm.difficult;

import java.util.Map;

public class NthMagicalNumber878 {


    /**
     * O(n)超时
     */
    public static int nthMagicalNumber(int n, int a, int b) {
        long mod = (long) (1e9 + 7);
        if (a % b == 0) {
            return (int) ((long) n * b % mod);
        }
        if (b % a == 0) {
            return (int) ((long) n * a % mod);

        }
        long result = 0;
        //multiple
        int x = 1;
        int y = 1;
        for (int m = 0; m < n; m++) {
            long res1 = (long) a * x % mod;
            long res2 = (long) b * y % mod;
            if (res1 == res2) {
                x++;
                y++;
                result = res1;
            } else if (res1 < res2) {
                x++;
                result = res1;
            } else {
                y++;
                result = res2;
            }
        }
        return (int) result;
    }


    public static void main(String[] args) {
//        System.out.println(nthMagicalNumber(5, 2, 4));
//        System.out.println(nthMagicalNumber(3, 8, 3));
        System.out.println(nthMagicalNumber(8, 10, 5));
    }


    /**
     * https://leetcode.cn/problems/nth-magical-number/solutions/1984641/er-fen-da-an-rong-chi-yuan-li-by-endless-9j34/
     * 二分法
     */
    private static final long MOD = (long) 1e9 + 7;

        public int nthMagicalNumber2(int n, int a, int b) {
            long lcm = a / gcd(a, b) * b;
            long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right)
            while (left + 1 < right) { // 开区间不为空
                long mid = left + (right - left) / 2;
                if (mid / a + mid / b - mid / lcm >= n)
                    right = mid; // 范围缩小到 (left, mid)
                else
                    left = mid; // 范围缩小到 (mid, right)
            }
            return (int) (right % MOD);
        }

        private int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

}
